The adsorption dynamics of a colloidal particle at a fluid interface is studied theoretically and numerically, documenting distinctly different relaxation regimes. The adsorption of a perfectly smooth particle is characterized by a fast exponential relaxation to thermodynamic equilibrium where the interfacial free energy has a minimum. The short relaxation time is given by the ratio of viscous damping to capillary forces. Physical and/or chemical heterogeneities in a colloidal system, however, can result in multiple minima of the free energy giving rise to metastability. In the presence of metastable states we observe a crossover to a slow logarithmic relaxation reminiscent of physical aging in glassy systems. The long relaxation time is determined by the thermally-activated escape rate from metastable states. Analytical expressions derived in this work yield quantitative agreement with molecular dynamics simulations and recent experimental observations. This work provides new insights on the adsorption dynamics of colloidal particles at fluid interfaces.